package com.dmall.graph.hamilton;

/**
 * 使用状态压缩解决
 * @author: xiao1.wang
 * @date: 2022/7/30 22:56
 */
public class Solution980_1 {

    private int[][] grid;
    private int R, C;
    private int start, end;
    private int left;

    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        this.R = grid.length;
        this.C = grid[0].length;
        this.left = R * C;

        for (int x = 0; x < R; x++) {
            for (int y = 0; y < C; y++) {
                if (grid[x][y] == 1) {
                    start = x * C + y;
                    grid[x][y] = 0;
                } else if (grid[x][y] == 2) {
                    end = x * C + y;
                    grid[x][y] = 0;
                } else if (grid[x][y] == -1) {
                    left --;
                }
            }
        }
        int visited = 0;
        return dfs(visited, start, left);
    }

    private int dfs(int visited, int v, int left) {
        int x = v / C;
        int y = v % C;
        visited += (1 << v);
        left --;
        if (left == 0 && v == end) {
            return 1;
        }
        int res = 0;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dirs[i][0];
            int nexty = y + dirs[i][1];
            int next = nextx * C + nexty;
            if (inArea(nextx, nexty) && ((visited & (1 << next)) == 0) && grid[nextx][nexty] != -1) {
                res += dfs(visited, next, left);
            }
        }
        return res;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }
}
